package com.bee.剑指offer;

import java.util.Arrays;

public class 合并两个有序的数组 {

    public static void merge(int A[], int m, int B[], int n) {
        int ia = 0;
        int ib = 0;
        int index = 0;
        int[] temp = new int[m + n];
        while (ia < m && ib < n && A[ia] != 0) {
            if (A[ia] <= B[ib]) {
                temp[index] = A[ia];
                ia++;
            } else {
                temp[index] = B[ib];
                ib++;
            }
            index++;
        }
        while (ia < A.length) {
            temp[index] = A[ia];
            ia++;
            index++;
        }
        while (ib < B.length) {
            temp[index] = B[ib];
            ib++;
            index++;
        }
        A = new int[m + n];
        for (int i = 0; i < m + n; i++) {
            A[i] = temp[i];
        }
        System.out.println(Arrays.toString(A));
    }

    /**
     * 双指针
     */
    public static void merge2(int A[], int m, int B[], int n) {
        int end = m + n - 1;
        // 分别从数据的尾部向前遍历，将大的元素添加到A数据末尾
        int ia = m - 1;
        int ib = n - 1;
        while (ia >= 0 && ib >= 0 && end >= 0) {
            if (A[ia] >= B[ib]) {
                A[end--] = A[ia--];
            } else {
                A[end--] = B[ib--];
            }
        }
        while (ia >= 0) {
            A[end--] = A[ia--];
        }
        while (ib >= 0) {
            A[end--] = B[ib--];
        }
        System.out.println(Arrays.toString(A));
    }


    public static void main(String[] args) {
        merge(new int[]{4, 5, 6}, 3, new int[]{1, 2, 3}, 3);
    }
}
